\documentclass[12pt, a4paper]{article}

\usepackage{sbc-template}

\usepackage{graphicx,url}

\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage[boxruled,linesnumbered,portuguese]{algorithm2e}

\sloppy

\title{Agrupamento de Dados em Séries Temporais Multidimensionais utilizando o
método Halite}

\author{Robson L. F. Cordeiro\inst{1}, Afonso E. da Silva\inst{1}}


\address{Instituto de Ciências Matemáticas e de Computação -- Universidade de
São Paulo (USP)\\
  Avenida Trabalhador São-Carlense, 400-Centro -- São Carlos -- SP -- Brasil
%\nextinstitute
%  Department of Computer Science -- University of Durham\\
%  Durham, U.K.  
%\nextinstitute
%  Departamento de Sistemas e Computação\\
%  Universidade Regional de Blumenal (FURB) -- Blumenau, SC -- Brazil
  \email{ robson@icmc.usp.br,
  aexpedito@grad.icmc.usp.br}
}


\begin{document} 

\maketitle

\begin{abstract}
  This meta-paper describes the style to be used in articles and short papers
  for SBC conferences. For papers in English, you should add just an abstract
  while for the papers in Portuguese, we also ask for an abstract in
  Portuguese (``resumo''). In both cases, abstracts should not have more than
  10 lines and must be in the first page of the paper.
\end{abstract}
     
\begin{resumo} 
  
  Neste artigo descrevemos como alteramos um trabalho previamente desenvolvido
  de modo a inlcuir novas funcionalidades e requisitos para atender às
  necessidades de um fluxo contínuo e potencialmente infinito dos dados, as
  \textit{data stream}. O trabalho que originalmente buscava por agrupamento de
  dados numa base de dados estática, agora permite realizar essa mesma tarefa
  sobre um fluxo intermitente dos dados proporcionando a mesma qualidade na
  precisão dos resultados finais.
  
\end{resumo}


\section{Introdução}

As tecnologias de base de dados permitem armazenar grandes volumes de informação
e são de vital importância para organizações, pois constituem o principal
componente de Sistemas de Informação dando suporte a operações de mineração de
dados, consultas complexas, operações de descoberta de conhecimento e
diversos outros tipos de análise de dados.

No entanto, esse modelo tradicional de base de dados finita e pouco dinâmica não
atende às necessidades de uma classe recente de aplicações, em que a informação
é representada como uma sequência (\textit{stream}) de valores potencialmente
ilimitada \cite{Elaine}.

Dentre estas aplicações destacam-se: gerenciamento e monitoramento em
redes de telecomunicação e de dados, monitoramento de tráfego na Internet,
transações financeiras, análise de mercado de ações, sistemas de segurança, e
análise de dados gerados por sensores, tais como medidas atmosféricas, 
medidas em processos industriais, medidas de tráfego em estradas, entre outras.

Essas aplicações capturam intermitentemente dados de eventos que ocorrem no meio
e muitas delas precisam de análises em tempo real para a tomada de decisão de
seus administradores.

Felizmente, a maioria dessas aplicações  não está interessada em extrair
conhecimento de todos os dados já coletados,  mas apenas analisar uma parcela
desses dados, considerando critérios como os  últimos \textit{N} eventos ou os
eventos capturados nos últimos \textit{T}  intervalos de tempo, e, portanto,
análises são viáveis na maioria dos casos reais.

Aplicações que necessitam armazenar um fluxo contínuo de informação em
tempo real armazenam aquilo que chamamos de \textit{data stream}.
Uma \textit{data stream} pode ser caracterizada como uma sequência de itens de
dados contínua, ordenada e potencialmente infinita. Mais especificamente, uma
\textit{data stream} pode ser definida como uma sequência de eventos $e$ em que
cada evento é representado por um conjunto de \textit{E} valores (atributos), tal
que $e_i = (a_1,a_2, \ldots, a_E)$ \cite{Elaine}.

Um conjunto finito de eventos resulta em uma série temporal multidimensional.
Essa pode conter um volume enorme de dados impossível  de armazenar em memória
primária e, portanto, deve ser analisada e posteriormente  armazenada em memória
secundária ou descartada.

Neste trabalho demonstraremos alguns dos resultados obtidos através da adição de
algumas funcionalidades sobre o trabalho desenvolvido em \cite{Cordeiro}, cujo
objetivo era desenvolver o algoritmo \textit{Halite} para realizar buscas
em dados estáticos de média a alta dimensionalidade.

Esse algoritmo implementa uma estrutura de dados que  forma o arcabouço dos
algoritmos baseados  na Teoria de Fractais, isto é, uma {\it quad-tree} 
multidimensional. Em estudos  preliminares que já realizamos indicam que o tempo
de construção dessa  estrutura equivale a aproximadamente 70\%  do tempo total
da análise, sendo este  o grande gargalo no processamento \cite{Cordeiro}.

O método proposto tenta implementar nessa estrutura de dados as funcionalidades
necessárias para reduzir seu tempo de contrução e  permitir que este mesmo
algoritmo analise séries temporais de dados semelhantes às citadas
anteriormente.

\section{Trabalhos Relacionados}

\section{Algoritmo Halite} 
\label{sec:halite}

O algoritmo Halite é uma técnica de agrupamento desenvolvido em
\cite{Cordeiro}, no qual permite a busca precisa, rápida e escalável por
agrupamentos em dados estáticos de média a alta dimensionalidade.

Para descrever essa técnica podemos dividi-la em duas prinpipais fases: a
primeira responsável por representar numa estrutrura de dados os eventos
contidos numa \textit{data stream} e a segunda responsável por analisar
essa estrutura em busca de agrupamentos ou \textit{clustering}

\subsection{Primeira fase}

A fase inicial do algoritmo Halite envolve a construção de uma estrutura de
dados, uma \textit{quad-tree} multidimensional (Counting-Tree) armazenada em
memória primária. Essa árvore representa uma base de dados $^dS$ de $n$ eventos
cujo número de atributos de cada evento é $d$. Nessa árvore cada  atributo
contém um valor numérico real normalizado entre o intervalo $[0,1)$ 
representado num espaço de $d$ dimensões, ou seja, uma dimensão para  cada
atributo da base de eventos.

O número de níveis ou resoluções da árvore $H$ é dado de acordo com a
necessidade da aplicação. O nó root (nível 0) representa a base de dados como
um todo e é subdividido em $2^d$ hipercubos no próximo nível (nível 1), nível
em que cada hipercubo apresenta metade do tamanho total do nível anterior. Mais
uma vez, o nível 2 apresenta $2^d$ hipercubos cada um com metade do tamanho dos
hipercubos do nível anterior e assim por diante até o ultimo nível $H-1$.

Nesse contexto, cada hipercubo é representado como uma célula de contagem, sendo
que o nó root não é representado por nenhuma célula única, apenas o nível 1 em
diante contém $2^d$ células. A estrutura da célula basicamente é representada
com alguns campos como $loc, n, P[d], usedCell, ptr$. O campo $loc$ é um 
identificador único para uma célula em um nível, $n$ é o numero total de pontos
incidentes na célula, $P[d]$ é um vetor que armazena a contagem de pontos
na metade inferior da célula, $usedCell$ uma variável booleana e $ptr$ um
ponteiro para o próximo nível da árvore.

Na Counting-Tree um ponto incidente numa célula qualquer do espaço é
contabilizado nas respectivas células incidentes em cada nível. Para identificar
uma célula $a$ em um nível $h$ ($a_h$) devemos observar seu campo $loc$. Na
Figura \ref{fig:figura1} é apresentado em um espaço bidimensional a disposição
dos campos $loc$ de células e seus respectivos níveis.

\begin{figure}[ht]
\centering
\includegraphics[width=.3\textwidth]{Figura1.png}
\caption{Disposição das células em um espaço bidimensional}
\label{fig:figura1}
\end{figure}

A célula hachurada está no nível 3, logo para identificá-la nesse nível devemos
conhecer seu respectivo campo $loc$ que nesse caso é igual a $11$. Retornando
ao nível 2 encontramos sua célula mãe também de campo $loc$ igual a $11$ e sua
célula avó com campo $loc$ igual a $01$. Portanto, um ponto incidente sobre o
espaço bidimensional da célula hachurada ($a_3.loc=11$) deve ser contabilizado
em todas as suas células superiores que nesse caso deve ser o caminho na
sequência $a_1.loc=01, a_2.loc=11, a_3.loc=11$.

Para ilustrar essa contagem de pontos, a próxima figura (Figura
\ref{fig:figura2}) fornece uma representação de um espaço bidimensional com um
hipercubo de lado $1$. Nessa figura encontramos três pontos na parte superior do
hipercubo, sendo que cada um deles em uma célula do terceiro nível.

\begin{figure}[ht]
\centering
\includegraphics[width=.4\textwidth]{Figura2.png}
\caption{Disposição das células em um espaço bidimensional}
\label{fig:figura2}
\end{figure}

Uma representação gráfica  da estrutrura de dados (Counting-tree) para contar
esses pontos nesse espaço bidimensional é dado na próxima figura (Figura
\ref{fig:figura3}). 

Na Figura \ref{fig:figura3} visualizamos a estrutura de dados contendo um nó
\textit{root} logo no primeiro nível da figura, mais dois nós no nível $2$ logo
abaixo e dois nós no nível $3$. Sabendo-se que temos duas dimensões para
representar os dados ($d=2$) e portanto cada nó apresenta $2^d=4$ células
por nó.

\begin{figure}[ht]
\centering
\includegraphics[width=.7\textwidth]{Figura3.png}
\caption{Estrutura de dados utilizada para representar os pontos}
\label{fig:figura3}
\end{figure}



\subsection{Segunda fase}

A segunda fase do algoritmo Halite consiste basicamente na atividade de
\textit{clustering} cujo objetivo é procurar agrupamentos de dados em subespaços
de moderada a alta dimensionalidade \cite{Cordeiro}. O algoritmo particiona
dinamicamente o espaço das regiões analisadas e encontra os \textit{clusters}
baseado na variação da densidade dos dados nesse subespaço.

As densidades dos dados são armazenados na estrutura criada na primeira fase do
algoritmo. Cada nível dessa estrutura, portanto, representa os dados como um
\textit{hyper-grid} numa resolução específica.

Posteriormente, um processo de convolução é aplicado através de filtros de
Laplace para cada nível da árvore para localizar concentrações de pontos em cada
uma das dimensões.

Depois é aplicado a um determinado nível da árvore um novo filtro considerando
todas as dimensões da base para encontrar as regiões que apresentam maiores alterações
na densidade de pontos. Essas regiões podem indicar um \textit{cluster} dos
dados que devem ser analisadas todas as suas vizinhanças para concluir quais
dessas regiões pertencem a um determinado \textit{cluster} ou não.



\section{Método proposto}

O método proposto inclui algumas funcionalidades adicionais ao algortimo que
talvez melhore os tempos de execução e \textit{clustering} do algoritmo
original. Algumas dessas funcionalidades adicionais tentam aproximar nossa
aplicação daquelas mencionadas logo no inicio cujo objeivo é extrair
conhecimento de \textit{data streams}

%janela de eventos
%nao normalizacao dos dados
%expansao e contracao decorrentes da nao normalizacao dos dados

\subsection{Inclusão de janelas de eventos}

O algoritmo {\em Halite} original obtém os elementos (eventos, em nosso
contexto) de uma base de dados estática, de forma que é necessário ler
sequencialmente os eventos uma única vez até o final e então iniciar o processo
de agrupamento.

Para simular uma aplicação em que os eventos chegam em tempo real para análise
a base de dados estática original foi dividida em algumas partes com número de
eventos aproximadamente iguais de forma a aproximar nossa aplicação daquelas citadas
na introdução. Com isso, nossa aplicação inicia a leitura completa da primeira
parte e já pode iniciar um processo de agrupamento desses dados.

Em nosso contexto denominamos cada uma dessas partes da base de dados de janela
de eventos. Dependendo da aplicação o critério de escolha dessa
parcela da base de dados ou da \textit{data stream} fica a critério de seus
usuários podendo construí-las à partir dos últimos $N$ eventos capturados, ou
dos eventos capturados a cada intervalo de tempo $T$ e dentre muitas outras
possibilidades. 

Vale ressaltar também que ao iniciar nossa aplicação fica à cargo do usuário
definir o número de janelas que a aplicação deve armazenar para análise de forma
que as janelas mais antigas são descartadas. Por exemplo, se o usuário
especificar $3$ janelas nos parâmetros de inicialização, a aplicação irá ler e
armazenar a primeira janela, ler a segunda janela e armazenar, ler a terceira e
armazenar, e na quarta janela lida os dados da primeira janela serão sobescritos
e não serão considerados no processo de agrupamento seguinte.

Em vista que as \textit{data stream} são potencialmente infinitas, as janelas,
portanto, limitam a sequência de eventos a serem analisados e possibilitam uma
análise de dados em tempo real, uma vez que, analisamos apenas uma parcela dos
dados capturados.

Com a inclusão das janelas nesse algoritmo também obtivemos a possibilidade de
analisar os dados mais recentes sem a necessidade de reconstruir  toda a
estrutura de dados novamente como no algoritmo original, ou seja, sem
reconstruir a {\it quad-tree} multidimensional, que é a fase de maior custo
computacional do algoritmo \cite{Cordeiro}.

Dessa forma, o modelo de janelas empregado permitiu simularmos uma
aplicação que recebe eventos intermitentemente para análise sem a necessidade de
realizarmos operações relativamente caras numa base de dados estática e em
constantes atualizações.

Para isso alguma alterações na estrutura de dados descrita na seção
\ref{sec:halite} foram implementadas, algumas delas referentes aos campos das
células na árvore. O campo $n$ que anteriormente armazenava a contagem de pontos
incidentes no subespaço da célula agora armazena essa mesma contagem, mas leva
em consideração também o número da janela que esses pontos pertencem, ou seja,
esse campo se tranformou em um vetor onde cada posição refere-se a uma janela.

Precisamos adicionar também mais uma dimensão para o campo $P[i]$ da célula que
anteriormente armazenava a contagem de pontos na metade inferior de uma célula
para uma dimensão $i$. Agora esse campo é uma matriz de duas dimensões cuja
representação aqui pode ser assim: $P[i][j]$, onde $i$ representa a dimensão e
$j$ a janela correspondente àquele ponto.

O Algoritmo \ref{alg:inserejanela} descreve como é realizado a operação de
inserção de uma janela na árvore. As operações de expansão e contração são
descritas nas seções posteriores.

\begin{algorithm}[H]
\label{alg:inserejanela}
\caption{InsereJanela($eventosDaJanela, janela$)}
\Entrada{Eventos da janela lida e janela atual}
\Saida{Janela de eventos inserida na árvore}
\Inicio
{
	Descarta dados da janela atual (mais antiga)\;
	\For{Cada evento $e$ da janela}
	{
		\If{As coordenadas $a_i$ do evento $e$ incidem fora do hipercubo}
		{
			Expande a árvore para representar esse evento\;
		}
		Insere evento $e$ na janela atual\;
	}
	
	\If{A árvore pode ser contraída}
	{
		Contrai a árvore\;
	}

}
\end{algorithm}


\subsection{Análise de dados não normalizados}

No algoritmo {\em Halite} original,  um processo de normalização é aplicado aos
atributos dos eventos para transformar os valores reais de entrada  em valores
reais dentro do intervalo $[0, 1)$. Os dados normalizados são então inseridos na
estrutura de dados.

No entanto, pretendemos capturar os atributos de cada evento sem
realizar qualquer tipo de normalização, pois conforme os dados são capturados
esses podem assumir qualquer valor, ou seja, numa eventualidade um atributo de
um evento pode assumir um valor inesperado para a estrutura de dados e assim
invalidar os dados normalizados até então.

Para solucionar esse problema criamos um intervalo com um valor máximo e mínimo
para cada dimensão em que um atributo é relacionado para a estrutura de dados.
Dessa forma, quando um atributo de um evento incide fora desse intervalo a
árvore precisa realizar um procedimento descrito na próxima subseção de
expansão de seu espaço de representação.

Com isso podemos inserir na estrutura de dados os atributos diretamente como
foram capturados sem qualquer normalização dos valores para algum intervalo 
especifico real.

Portanto, esperamos aumentar a precisão dos resultados finais, uma vez que estes
dados não sofrerão qualquer alteração no decorrer da execução da aplicação.

\subsection{Expansão e contração do espaço de representação}

Em vista que os atributos dos eventos assumem valores no intervalo dos números
reais, foi necessário criar para a estrutura de dados um método para ajustar
os intervalos de uma dimensão para capturar os eventos que não incidem sobre
esse intervalo inicial.

Por exemplo, sabendo que cada atributo da \textit{data stream} é associado a uma
dimensão da árvore, quando inserimos a primeira janela de eventos a
própria estrutura de dados se  encarrega de determinar o intervalo inicial que
ela irá adotar para cada dimensão de forma a representar todos os
eventos presentes nessa janela.

Passado essa fase inicial e da chegada da segunda janela de eventos, se a
dimensão $x$ da árvore estiver no intervalo $[1, 3]$ e o próximo
evento conter uma coordenada $x$ igual a $4$ a estrutura deverá realizar
uma operação de expansão para representar esse evento. A estrutura de dados
realiza essa operação até conseguir representar todas as coordenadas do evento
e depois insere esse ponto em sua estrutura.

No caso da contração do espaço de representação, essa operação realiza o
procedimento contrário à expansão de forma a eliminar da memória principal
todos os espaços desnecessários para o funcionamento da atividade de
agrupamento.

A seguir é apresentado o Algoritmo \ref{alg:expande} de expansão  do espaço de
representação da estrutura implementada. Note que muitas das mudanças
implementadas estão representadas nesse e nos algoritmos seguintes. As letras
$L_i$ e $H_i$ referem-se respectivamente ao limite mínimo e máximo para uma
dimensão $i$. São esses valores mínimos e máximos que se alteram numa expansão
ou contração da árvore segundo um fator especificado aqui como $r0$. Esse fator
dobra a cada expansão ou é dividido por dois numa contração, também podemos
compreender ele como a diferença $H_i - L_i$ para todas as dimensões $i$.

\begin{algorithm}[H]
\label{alg:expande}
\caption{Expande($a$)}
\Entrada{Coordenadas $a_i$ do evento $e$}
\Saida{Árvore expandida}
\Inicio
{		
	\If{As coordenadas $a_i$ de $e$ estão fora do hipercubo}
	{
		\For {Cada coordenada $a_i$ do evento $e$}
		{
	  		\uIf{$a_i$ é menor do que o valor mínimo da dimensão $i$}
	  		{
	  			$L_i=L_i-r0$\;
	  		}
	  		\Else
	  		{
	  			$H_i=H_i+r0$\;
	  		}
		}
		
		$r0=r0*2$\;
		$aux=raiz$\;
		$raiz=new(nodo)$\;
		$raiz\rightarrow nextLevel=aux$\;
		
		\For{Cada dimensão $i$}
		{
			\For{Cada janela $j$}
			{
				\uIf{Se $a_i$ era menor do que $L_i$}
				{
					$P[i][j]=n[j]$\;
				}
				\Else
				{
					$P[i][j]=0$\;
				}
			}
		}
		$Expande($a$)$\;
	}
	
}
\end{algorithm}

No Algoritmo \ref{alg:contrai} a seguir é dado o algoritmo de contração da
árvore:

\begin{algorithm}[H]
\label{alg:contrai}
\caption{Contrai($c$)}
\Entrada{Única célula $c$ restante no nodo raíz}
\Saida{Árvore contraída}
\Inicio
{		
	\If{A árvore pode ser contraída}
	{
		$r0=r0/2$\;
		\For{Cada dimensão $i$}
		{
			\uIf{$c$ está na metade superior da dimensão $i$}
			{
				$L_i=L_i+r0$\;
			}
			\Else
			{
				$H_i=H_I-r0$\;
			}
		}
		
		\For{Cada dimensão $i$}
		{
			\For{Cada janela $j$}
			{
				$P[i][j]=c\rightarrow P[i][j]$\;
			}
		}
		$aux=raiz$\;
		$raiz=c\rightarrow nextLevel$\;
		$delete(aux)$\;
		
	}
	
}
\end{algorithm}


\section{Experimentos}

\subsection{Algoritmo original}

\subsection{Algoritmo modificado}

Nos testes realizados cada janela contém um número aproximado
de eventos de forma que as janelas mais recentes registram os eventos mais
recentes no tempo.

\section{Conclusão}


\bibliographystyle{sbc}
\bibliography{sbc-template}

\end{document}

